package codeRandomThoughts.Test718最长重复子数组;

public class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int maxLen = 0;

        //dp[i][j]:以nums1[i]为结尾和以nums2[j]为结尾的公共最长子数组的长度
        int[][] dp = new int[nums1.length][nums2.length];

        //初始化
        //j=0
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                maxLen = 1;
            }
        }
        //i=0
        for (int j = 0; j < nums2.length; j++) {
            if (nums2[j] == nums1[0]) {
                dp[0][j] = 1;
                maxLen = 1;
            }
        }

        if (nums1.length == 1 || nums2.length == 1) {
            return maxLen;
        }

        //递推
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                }
            }
        }

        return maxLen;
    }
}
